import collections
from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        solutions = []
        # 设置特定长度的列表，表示占用情况棋盘占用情况
        cols = [False] * n
        diag1 = [False] * (2 * n - 1)
        diag2 = [False] * (2 * n - 1)

        path = []

        def drawback(row):
            if row == n:  # 所有行遍历
                res = []
                for col_index in path:
                    s = ['.'] * n
                    s[col_index] = 'Q'
                    res.append(''.join(s))  # 将元素拼接为字符串
                solutions.append(res)
                return

            for col in range(n):
                # 索引
                d1 = row - col + (n - 1)  # 正对角线
                d2 = row + col  # 反掉对角线

                if diag1[d1] or diag2[d2] or cols[col]:
                    continue

                path.append(col)  # 该列存入路径
                diag1[d1] = True
                diag2[d2] = True
                cols[col] = True

                drawback(row + 1)  # 下一行

                path.pop()  # 撤销本次
                diag1[d1] = False
                diag2[d2] = False
                cols[col] = False

        drawback(0)
        return solutions
